import java.util.Arrays;

/**
 * Created With IntelliJ IDEA
 * Description:牛客网：BM70 兑换零钱(一)
 * <a href="https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45?tpId=295&tqId=988994&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj">...</a>
 * User: DELL
 * Data: 2022-11-07
 * Time: 12:56
 */

//        step 1：可以用dp[i]表示要凑出i元钱需要最小的货币数。
//        step 2：一开始都设置为最大值aim+1，因为货币最小1元，即货币数不会超过aim+1.
//        step 3：初始化dp[0]=0。
//        step 4：后续遍历1元到aim元，枚举每种面值的货币都可能组成的情况，取每次的最小值即可，
//                转移方程为dp[i]=min(dp[i],dp[i−arr[j]] + 1).
//        step 5：最后比较dp[aim]的值是否超过aim，如果超过说明无解，否则返回即可。
public class Solution {
    public int minMoney (int[] arr, int aim) {
        //判空处理
        if (arr.length == 0) {
            return -1;
        }
        //创建dp数组
        int[] dp = new int[aim + 1];
        //设置初始值为aim + 1
        Arrays.fill(dp,aim + 1);
        //初始化dp[0] = 0
        dp[0] = 0;
        //遍历dp数组，枚举每种面值的货币都可能组成的情况
        for (int i = 1; i < aim + 1; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (arr[j] <= i) {
                    dp[i] = Math.min(dp[i],dp[i - arr[j]] + 1);
                }
                //当arr[j] > i时，dp[i]的值不变
            }
        }
        //判断是否无解并返回
        if (dp[aim] == aim + 1) {
            return -1;
        } else {
            return dp[aim];
        }
    }
}
